[BAEKJOON] 2225. 합분해

문제 :

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력 :

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력 :

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이 :

오랜만에 DP 문제를 푸는 거라서 조금은 쉬운 문제에 접근했다.

본 문제는 숫자의 순서를 고려하여 0~n개 사이의 숫자를 k개 나열하여 n을 만들 수 있는 경우의 수를 찾는 문제이다.

본 문제는 완전 탐색으로는 200^200이라는 엄청나게 큰 시간 복잡도가 걸리기 때문에 무조건 dp 방식을 활용해 주어야 했다.

따라서 dp[k][n] (k개의 숫자들로 n을 만들어 낼 수 있는 경우의 수) 배열을 구현하고,

• dp[k][n] += dp[k-1][i] (0 ≤ i ≤ n)

점화식을 다음과 같이 설계했다. 총 3중 for문이 돌아가긴 하지만 완전 탐색과 비교하여 매우 짧은 시간 안에 문제를 해결할 수 있었다.

코드 :

#include <iostream>

#define ll long long
#define DVD 1000000000

using namespace std;
ll dp[201][201];

int main() {
    int n, k, i, j, t;
    cin >> n >> k;
    fill_n(dp[1], n + 1, 1);
    for (i = 2; i <= k; i++)
        for (j = 0; j <= n; j++)
            for (t = 0; t <= j; t++)
                dp[i][j] = (dp[i][j] + dp[i - 1][t]) % DVD;
    cout << dp[k][n] << '\n';
    return 0;
}